package com.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 40. 组合总和 II
 * 给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 * candidates中的每个数字在每个组合中只能使用一次。
 * 注意：解集不能包含重复的组合。
 * 示例1:
 * 输入: candidates =[10,1,2,7,6,1,5], target =8,
 * 输出:
 * [
 * [1,1,6],
 * [1,2,5],
 * [1,7],
 * [2,6]
 * ]
 * 示例2:
 * 输入: candidates =[2,5,2,1,2], target =5,
 * 输出:
 * [
 * [1,2,2],
 * [5]
 * ]
 * 提示:
 * 1 <=candidates.length <= 100
 * 1 <=candidates[i] <= 50
 * 1 <= target <= 30
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年11月22日 16:11
 */
class Code40 {
    public static void main(String[] args) {
        int[] candidates = new int[]{10,1,2,7,6,1,5};
        Code40 code = new Code40();
        List<List<Integer>> lists = code.combinationSum2(candidates, 8);
        System.out.println(lists);
    }
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    int sum = 0;
    boolean[] flag = null;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        flag = new boolean[candidates.length];
        dfs(candidates,target,0);
        return list;
    }
    public void dfs(int[] candidates, int target,int index){
        if(sum == target){
            list.add(new ArrayList<>(temp));
            return;
        }
        if(index >= candidates.length){
            return;
        }
        //剪枝操作：如果 sum + candidates[i] > target 就终止遍历
        for(int i=index;i<candidates.length && sum + candidates[i] <= target;i++){
            if(i>0 && !flag[i-1] && candidates[i] == candidates[i-1]){
                continue;
            }
            sum += candidates[i];
            temp.add(candidates[i]);
            flag[i] = true;
            dfs(candidates,target,i+1);
            sum -= candidates[i];
            temp.remove(temp.size()-1);
            flag[i] = false;
        }
    }
}
